#ifndef _DYNAMICARRAY_H_
#define _DYNAMICARRAY_H_

class DynamicArray
{
public:
    using ElementType = void *;
    DynamicArray();
    void SetFreePtr(void (*FreePtr)(ElementType))
    {
        this->FreePtr = FreePtr;
    }
    void SetShowPtr(void (*ShowPtr)(ElementType))
    {
        this->ShowPtr = ShowPtr;
    }
    void SetCompare(bool (*Compare)(ElementType, ElementType))
    {
        this->Compare = Compare;
    }
    void SetCompareBig(bool (*CompareBig)(ElementType, ElementType))
    {
        this->Compare = Compare;
    }
    // 尾插
    void InsertTail(const ElementType &element);
    // 头插
    void InsertHead(const ElementType &element);
    // 中间插入法
    void InsertByIndex(const ElementType &element, int index);

    void show();
    DynamicArray(const DynamicArray &DArray);
    DynamicArray &operator=(const DynamicArray &DArray);
    // 按下标查找
    ElementType FindByIndex(int index);
    ElementType &operator[](int index);
    // 按值查找
    DynamicArray FindElement(const ElementType &element);
    // 按下标删除
    void RemoveByIndex(int index);
    // 按值删除
    void RemoveByElement(ElementType element);

    // int SearchElement(ElementType element);
    //  按下标修改
    void UpdateByIndex(int index, const ElementType &element);
    // 按值修改
    void UpdateByElement(const ElementType &oldValue, const ElementType &newValue);

    // 排序：递归深度  2*log2n
    void Sort();
    // 去重算法：去除数列中的相同值，只留一个
    void Duplicate();
    // 合并两个有序数列
    DynamicArray Merge(const DynamicArray &a);
    // 找交集
    DynamicArray FindInterSection(const DynamicArray &array);
    // 找并集
    DynamicArray FindUnionSet(const DynamicArray &array);
    // 找补集
    DynamicArray FindDifference(const DynamicArray &array);

    // 判断两个数列是否相等
    bool operator==(const DynamicArray &array);

    int BinarySearch(const ElementType &element);

    // 判断是不是一个子数列
    bool IsChild(const DynamicArray &array);
    // 是否是连续子序列
    bool IsConChild(const DynamicArray &array);
    // 获取一个子序列
    DynamicArray subsquence(int index, int len);

    int Size();

    ~DynamicArray();

private:
    void FastSort(int start, int end, int deepth, int MaxDepth);
    void InsertSort(int start, int end);
    int Partition(int start, int end);

    ElementType *a;
    int capacity;
    int size;
    void (*FreePtr)(ElementType);
    void (*ShowPtr)(ElementType);
    bool (*Compare)(ElementType, ElementType);
    bool (*CompareBig)(ElementType, ElementType);
};

void Show(DynamicArray::ElementType element);
void ShowChar(DynamicArray::ElementType element);
void ShowInt(DynamicArray::ElementType element);
void Free(DynamicArray::ElementType element);
bool Compare(DynamicArray::ElementType ptr, DynamicArray::ElementType str);
bool Compare1(DynamicArray::ElementType ptr, DynamicArray::ElementType str);
void ShowIntNum(DynamicArray::ElementType element);

#endif